package uestc.lj.basic.sort;

/**
 * 使用归并排序求出数组的最小和
 * 所谓最小和即数组中每个数的左边比起小的和
 *
 * @Author:Crazlee
 * @Date:2021/11/20
 */
public class Code08_smallSumbyMergeSort {

    public static int smallSum(int[] array) {
        if (array == null || array.length < 2) {
            return 0;
        }
        return process(array, 0, array.length - 1);
    }

    private static int process(int[] array, int left, int right) {
        if (left == right) {
            return 0;
        }
        int mid = left + ((right - left) >> 1);
        return process(array, left, mid) + process(array, mid + 1, right) + merge(array, left, mid, right);
    }

    /**
     * 合并中有一个细节问题就是：
     * 当左边和右边数组中数相同的时候，要先移动右边数组。
     * 这样才可以通过常数的时间复杂度求出右边的小数和
     *
     * @param array 数组
     * @param left  左边界
     * @param mid   中间位置
     * @param right 有边界
     * @return 小数和
     */
    private static int merge(int[] array, int left, int mid, int right) {
        int[] help = new int[right - left + 1];
        int ans = 0;
        int i = 0;
        int p1 = left;
        int p2 = mid + 1;
        while (p1 <= mid && p2 <= right) {
            ans += array[p1] < array[p2] ? (right - p2 + 1) * array[p1] : 0;
            //细节问题：当左右相等时，要先把右侧数加入help数组中
            help[i++] = array[p1] < array[p2] ? array[p1++] : array[p2++];
        }
        while (p1 <= mid) {
            help[i++] = array[p1++];
        }
        while (p2 <= right) {
            help[i++] = array[p2++];
        }
        System.arraycopy(help, 0, array, left, help.length);
        return ans;
    }

    public static void main(String[] args) {
        int[] array = {1, 3, 2, 5, 4};
        int smallSum = smallSum(array);
        System.out.println("array数组的小数和是：" + smallSum);
    }
}
